package arithmetic.demo16;

/**
 * 动态规划： 二维dp + 分两段区间讨论 :让字符串成为回文字符串的最小插入次数
 */
class Solution {
    public int minInsertions(String s) {
        //  动态规划 + 分类讨论
         int len = s.length();
         int[][] dp = new int[len][len];

         // 自上而下，自左而右天不能
         for(int i = len - 1; i >= 0; i--) {
            for(int j = i ; j < len; j++) {
                //  判断首尾元素是否相等
                 if(s.charAt(i) == s.charAt(j)) {
                    //   如果相等分: 相同， 相邻， 含中间元素
                      dp[i][j] =  i + 1 < j ? dp[i+1][j-1]  : 0; 
                 } else {
                    // 如果不相等。 
                    //  加左，s[j] + [i, j-1]
                    // 加右， s[i] + [i+1,j]
                    // 最终取最小次数
                        dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
                 }
            }
         }

        //  最终返回回文串的整个区间
        return dp[0][len-1];
    }
}